2A
弱智题,硬判即可。
Code
热爱 Coding 的普通人
初三了还没有普及组一等,被所有人吊打。
弱智题,不断用 l 除以 k 即可。
#include <cstdio>
int k, l, cnt;
int main() {
scanf("%d%d", &k, &l);
while (l % k == 0) cnt++, l /= k;
if (l == 1) printf("YES\n%d\n", cnt - 1);
else puts("NO");
}
看到数据范围 n≤16 考虑状压,直接暴力枚举子集判断是否有冲突即可。
时间复杂度 O(n22n) 。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 20;
string s[N], a, b;
int f[N][N], n, m, ans;
int find(string str) {
int i = 0;
while (str != s[i]) i++;
return i;
}
int popcount(int x) {
int ret = 0;
while (x) ret += x & 1, x >>= 1;
return ret;
}
int main() {
cin >> n >> m;
for (int i = 0; i <= n - 1; i++) cin >> s[i];
sort(s, s + n);
for (int i = 1; i <= m; i++) {
cin >> a >> b;
int u = find(a), v = find(b);
f[u][v] = f[v][u] = 1;
}
for (int s = 0; s <= (1 << n) - 1; s++) {
int flag = 0;
for (int i = 0; i <= n - 1; i++) {
if ((s >> i & 1) == 0)
continue;
for (int j = i + 1; j <= n - 1; j++) {
if ((s >> j & 1) == 0)
continue;
flag |= f[i][j];
if (flag) break;
}
if (flag) break;
}
if (flag == 0) {
if (popcount(s) > popcount(ans))
ans = s;
}
}
cout << popcount(ans) << endl;
for (int i = 0; i <= n - 1; i++) {
if (ans >> i & 1)
cout << s[i] << endl;
}
}
大模拟,不知道为什么死活写不对。
搬一个题解代码。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
char s[N], word[N];
int type[N], tp, p, flag, cnt, len, t;
int modify() {
int l = strlen(word);
if (l < 3) return 0;
if (strcmp(word + l - 4, "lios") == 0) return 1;
if (strcmp(word + l - 5, "liala") == 0) return -1;
if (strcmp(word + l - 3, "etr") == 0) return 2;
if (strcmp(word + l - 4, "etra") == 0) return -2;
if (strcmp(word + l - 6, "initis") == 0) return 3;
if (strcmp(word + l - 6, "inites") == 0) return -3;
return 0;
}
int main() {
cin.getline(s, N);
flag = 1;
len = strlen(s);
for (int i = 0; i <= len; i++) {
if (s[i] != ' ' && s[i] != '\0')
word[p++] = s[i];
else {
word[p] = '\0';
cnt++;
t = modify();
if (t != 0) type[tp++] = t;
else {
flag = 0;
break;
}
}
}
if (cnt == 1 && flag == 1) {
puts("YES");
return 0;
}
if (flag == 0) {
puts("NO");
return 0;
}
cnt = 0;
for (int i = 0; i < tp; i++) {
if (abs(type[i]) == 2)
cnt++;
}
if (cnt != 1) {
puts("NO");
return 0;
}
flag = 1;
if (type[0] < 0) {
for (int i = 1; i < tp; i++)
if (type[i] > 0) {
flag = 0;
break;
}
}
else {
for (int i = 1; i < tp; i++)
if (type[i] < 0) {
flag = 0;
break;
}
}
if (flag == 0) {
puts("NO");
return 0;
}
flag = 1;
for (int i = 1; i < tp; i++) {
if (abs(type[i]) < abs(type[i - 1])) {
flag = 0;
break;
}
}
if (flag) puts("YES");
else puts("NO");
}